package LearnAlgorithm.d_标准查找算法and标准排序算法;

import java.util.HashMap;

public class b5d快速排序by双向扫描分区方式plus绝对中值优化plus小数组插入排序优化 {
	public static void main(String[] args) {
//		int[] arr = new int[] {6,8,7,9,5,4,3,6};
		int[] arr = new int[] {7,2,3,5,9,9,9};
		long before = System.currentTimeMillis();
//		quickSort(arr, 0, arr.length-1);
		quickSortMyself(arr, 0, arr.length-1);
		
		util.Util.duration(before);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	public static void quickSortMyself(int[] arr, int p, int r) {//使用递归
		if (p < r) {
			if (r - p + 1 <= 8) {
				insertSort(arr, p, r);
			} else {
				int q = partitionMyself(arr, p, r);//核心语句在这行，即找出主元
				quickSortMyself(arr, p, q-1);//对主元左边排序
				quickSortMyself(arr, q+1, r);//对主元右边排序
			}
		}
	}
	
	/**
	 * 快速排序
	 * O(NlogN)
	 * @param arr
	 * @param p
	 * @param r
	 */
	public static void quickSort(int[] arr, int p, int r) {//使用递归
		if (p < r) {
			if (r - p + 1 <= 8) {
				insertSort(arr, p, r);
			} else {
				int q = partition(arr, p, r);//核心语句在这行，即找出主元
				quickSort(arr, p, q-1);//对主元左边排序
				quickSort(arr, q+1, r);//对主元右边排序
			}
		}
	}
	
	/**
	 * 自己的partition思想
	 * 不再取首值作为主元
	 * @param arr
	 * @param p
	 * @param r
	 * @return
	 */
	public static int partitionMyself(int[] arr, int p, int r) {
		int midIndex = getMedian(arr, p, r);
		int pivot = arr[midIndex];
		while (p <= r) {
			while (p <= r && arr[p] <= pivot) {
				p++;
			}
			while (p <= r && arr[r] > pivot) {
				r--;
			}
			if (p < r) {
				swap(arr, p, r);
			}
		}
		return r;
	}
	
	/**
	 * 快速排序核心---设置主元并把主元放在相对居中的位置
	 * 同时使用了优化，绝对中值优化
	 * 老师的思想---主元是首值
	 * @param arr
	 * @param p
	 * @param r
	 * @return bigger
	 */
	public static int partition(int[] arr, int p, int r) {
		int midIndex =  getMedian(arr, p, r);//寻找绝对中值的索引，使用了插入排序
		swap(arr, p, midIndex);//把绝对中值与首值进行交换
		int pivot = arr[p];//定义首值作为主元pivot
		//以上三行代码可以修改为下面这一行代码：
		//但是我们优化前的快速排序的sp是从p+1开始的，要修改的话可能花费时间，所以我们才大费周章把绝对中值的索引求出来，进而把绝对中值与首值进行交换(虽然直接修改重构快速排序的代码可能会更省时间就是了)
//		int pivot2 = arr[getMedian(arr, p, r)];
		
		int sp = p+1;//定义右移指针
		int bigger = r;//定义左移指针
		
		while (sp <= bigger) {//只要sp>bigger那么就是交错了，就可以退出循环
			//都加上“sp <= bigger && ”是为了防止越界
			while (sp <= bigger && arr[sp] <= pivot) {//循环退出时，sp一定是指向第一个大于主元的值
				sp++;
			}
			while (sp <= bigger && arr[bigger] > pivot) {//循环退出时，bigger一定是指向最后一个小于等于主元的值
				bigger--;
			}
			if (sp < bigger) {//为什么不加上<=判断；是因为如果sp==bigger时，还去交换arr[sp]与arr[bigger]，是没意义的，加上判断能提升运行效率
				swap(arr, sp, bigger);//这里交换arr[sp]与arr[bigger],
			}
		}
		/*
		 * while(sp <= bigger)退出时，sp/bigger两者交错，
		 * 且bigger指向的是最后一个小于等于主元的位置，
		 * 也就是主元应该呆的位置
		 */
		swap(arr, p, bigger);//这里理论上也能改进，如arr[p]==arr[biger],如p==bigger的情况，但是我不改进了，我怕出错
		return bigger;//最后返回主元所在的索引
	}
	
	
	
	/**
	 * 寻找(宏观上相对的)绝对中值
	 * @param arr
	 * @param p
	 * @param r
	 * @return
	 */
	public static int getMedian(int[] arr, int p, int r) {
		int size = (r - p) + 1;//传入的数组片段长度
		int groupSize = (size % 5 == 0) ? (size / 5) : ((size / 5) + 1);//每5个元素一组，总共有多少组
		int medians[] = new int[groupSize];//保存所有组的中值的数组
		HashMap<Integer, Integer> mediansValue_index = new HashMap<Integer,Integer>();//生成所有需要保存的中值的“数值:索引”map集合
		int indexOfMedians = 0;
		for (int j = 0; j < groupSize; j++) {
			if (j == (groupSize - 1)) {//优先考虑最后一组的情况，因为最后一组可能不是5个数
				insertSort(arr, (p + (j * 5)), r);//排序最后一组
				medians[indexOfMedians++] = arr[(p + (j * 5) + r) >>> 1];//把最后一组的中值存入特定数组，除法向下取整
				mediansValue_index.put(arr[(p + (j * 5) + r) >>> 1], (p + (j * 5) + r) >>> 1);
			} else {//其他的普通情况，都是5个数
				insertSort(arr, (p + (j * 5)), ((p + (j * 5)) + 4));
				medians[indexOfMedians++] = arr[((p + (j * 5)) + 2)];
				mediansValue_index.put(arr[((p + (j * 5)) + 2)], ((p + (j * 5)) + 2));
			}
		}
		insertSort(medians, 0, medians.length - 1);//对已经填入所有数值的“中值数组”进行插入排序
		return mediansValue_index.get(medians[medians.length >>> 1]);//根据key(即中值数组的中值)找出value(即中值数组的中值的索引)
	}
	
	/**
	 * 插入排序
	 * @param arr
	 * @param p
	 * @param r
	 */
	public static void insertSort(int[] arr, int p, int r) {
		int value_i = 0;
		int before_value_i = 0;
		for (int i = p + 1; i <= r; i++) {
			value_i = arr[i];
			before_value_i = i-1;
			while (before_value_i > p - 1 && value_i < arr[before_value_i]) {
				arr[before_value_i + 1] = arr[before_value_i];
				before_value_i--;
			}
			arr[before_value_i+1] = value_i;
		}
	}


	/**
	 * 交换值方法
	 * @param arr
	 * @param i
	 * @param j
	 */
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
	
	/***
	 * 快速排序核心————设置主元并把主元放在相对居中的位置
	 * @param arr
	 * @param p
	 * @param r
	 * @return bigger
	 */
	public static int partition_old(int[] arr, int p, int r) {
		int pivot = arr[p];//定义首值作为主元pivot
		int sp = p+1;//定义右移指针
		int bigger = r;//定义左移指针
		
		while (sp <= bigger) {//只要sp>bigger那么就是交错了，就可以退出循环
			//都加上“sp <= bigger && ”是为了防止越界
			while (sp <= bigger && arr[sp] <= pivot) {//循环退出时，sp一定是指向第一个大于主元的值
				sp++;
			}
			
			while (sp <= bigger && arr[bigger] > pivot) {//循环退出时，bigger一定是指向最后一个小于等于主元的值
				bigger--;
			}
			
			if (sp < bigger) {//为什么要加上<=判断；是因为如果sp==bigger时，还去交换arr[sp]与arr[bigger]，是没意义的，加上判断能提升运行效率
				swap(arr, sp, bigger);//这里交换arr[sp]与arr[bigger],
			}
		}
		/*
		 * //while(sp <= bigger)退出时，sp/bigger两者交错，且bigger指向的是最后一个小于等于主元的位置，也就是主元应该呆的位置
		 */
		swap(arr, p, bigger);//这里理论上也能改进，如arr[p]==arr[biger],如p==bigger的情况，但是我不改进了，我怕出错
		return bigger;//最后返回主元所在的索引
	}
}